/*
 * @lc app=leetcode.cn id=923 lang=cpp
 *
 * [923] 三数之和的多种可能
 */

// @lc code=start
class Solution
{
public:
    const int modNum = 1e9 + 7;

    int twoSumMulti(vector<int> &arr, int target, int l, int r)
    {
        int res = 0;
        while (l < r)
        {
            int sum = arr[l] + arr[r];
            if (sum < target)
            {
                l++;
            }
            else if (sum > target)
            {
                r--;
            }
            else
            {
                if (arr[l] == arr[r])
                {
                    int count = r - l + 1;
                    res += count * (count - 1) / 2;
                    res %= modNum;
                    break;
                }
                int lcnt = 1, rcnt = 1;
                while (l < r && arr[l] == arr[l + 1])
                {
                    lcnt++;
                    l++;
                }
                while (l < r && arr[r] == arr[r - 1])
                {
                    rcnt++;
                    r--;
                }
                res += lcnt * rcnt;
                res %= modNum;
                l++, r--;
            }
        }
        return res;
    }

    int threeSumMulti(vector<int> &arr, int target)
    {
        sort(arr.begin(), arr.end());
        int n = arr.size(), ans = 0;

        for (int i = 0; i < n - 1; i++)
        {
            ans += twoSumMulti(arr, target - arr[i], i + 1, n - 1);
            ans %= modNum;
        }

        return ans;
    }
};
// @lc code=end
